ATM (Asynchronous Transfer Mode) is the recommended transport technique for BISDN (Broadband Integrated Services Digital Network) to carry various traffics, such as video, voice, and data, by CCITT, an international standard body. ATM provides a flexible bandwidth, fast and dynamic reconfiguration of calls, service independency, and efficient multiplexing of bursty traffics. An ideal ATM switch is able to accommodate bursty traffic arising from various heterogeneous BISDN services without incurring intolerable delay and high hardware complexity.
Buffers are required in the packet switch for the temporary storage of transmitted packets. Buffering is primarily required for external and internal resource conflicts. An example of an external resource conflict occurs when two packets are to be transmitted on the same output port. In this case, typically one packet is transmitted and one is buffered. Internal conflicts occur when two packets require the same internal source, e.g. a wire internal to the switch.
Current switch designs incorporate either discrete input buffers, discrete output buffers, or internal buffering [M. G. Hluchy; and M. J. Karol, "Queuing in High-Performance Packet Switching" IEEE Journal on Selected Areas in Communications SAC-6, pp. 1587-1597, Dec. 1988]. For discrete input buffers, a queue is associated with each input port. Arriving packets are inserted at the bottom of the queue. The top packet is removed if no internal or external conflicts arise with other packets in he switch. Output buffering associates a similar queue with each output port. Internal buffering associates discrete buffers with internal switch structures, or stages. Results from previous studies (K. Lutz, "Considerations on ATM switching techniques," International Journal of Digital and Analog Cabled Systems, vol. 1, pp. 237-243, 1988; A. Eckberg and T. Hou, "Effects of output buffer sharing on buffer requirements in an ATDM packet switch," in Proc. of INFOCOM '88, (New Orleans, La.), IEEE, Mar. 1988, pp. 459-466; H. Kim and A. Leon-Garcia, "A multistage ATM switch with interstage buffers," International Journal of Digital & Analog Cabled Systems, vol. 2, pp. 289-301, Dec. 1989; H. Kim and A. Leon-Garcia, "Comparative performance study of ATM switches," in preparation for the Proceedings of the IEEE, 1990) indicate that sharing a common buffer lowers the packet loss probability of the switch dramatically. The improvement is expected to be even greater for bursty traffics.
The size and number of buffers utilized in the packet switch can have significant effects on its cost and performance. Large and high numbers of buffers have detrimental effects on complexity and cost. In addition, large buffers can significantly increase the delay required to transmit a packet from the switch. Small, discrete buffers can result in dropped packets due to buffer overflow. It is desirable to require buffers of small size, whose numbers grow linearly with the number of switch inputs or outputs.
Output buffering switches have the best performance in terms of throughput and packet delay under uniform traffic patterns. However, their high hardware complexity led to the study of input queuing switch structures which have lower hardware complexity (J. Hui and E. Arthurs, "A broadband packet switch for integrated transport," IEEE Journal on Selected Areas in Communications, vol. SAC-5, pp. 1264-1273, Oct. 1987.). In the present invention, a non-blocking input queuing switch architecture with a shared-memory input queue is presented. The simple shared-memory input queue allows the input ports to share a common buffer, thus absorbing bursty traffic without increased packet loss. Furthermore, the switch ensures that the packets are transmitted in the order that they are received, eliminating the resequencing problem at the end-user.